package prictise.com.application1.suanFa;

import org.junit.Test;

import java.util.Arrays;

/**
 * @Author zhisiyi
 * @Date 2021.04.14 14:53
 * @Comment
 */
public class UniquePath {

  public int uniquePaths(int m, int n) {
    //一维空间，其大小为 n
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        //等式右边的 dp[j]是上一次计算后的，加上左边的dp[j-1]即为当前结果
        dp[j] = dp[j] + dp[j - 1];
      }
    }
    return dp[n - 1];
  }

  /**
   * 组合的方式
   * @param m
   * @param n
   * @return
   */
  public int uniquePaths2(int m, int n) {
    long ans = 1;
    for (int x = n, y = 1; y < m; ++x, ++y) {
      ans = ans * x / y;
    }
    return (int) ans;
  }


  @Test
  public void test() {
    int ladder = uniquePaths2(3, 7);
    System.out.println(ladder);
  }
}
